#include <vector>
#include <iostream>
#include <stack>

using namespace std;

struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
};

class Solution 
{
public:
    bool isPalindrome(ListNode* head) 
    {
        if(head == nullptr)
        {
            return false;
        }
       stack<int> st;
       ListNode * cur = head;
       while(cur != nullptr)
       {
            st.push(cur->val);
            cur = cur->next;
       }
       cur = head;
       while(cur != nullptr)
       {
            if(cur->val != st.top())
            {
                return false;
            }
            st.pop();
            cur = cur->next;
       }
       if(st.empty())
       {
            return true;
       }
       else
       {
            return false;
       }
    }
};

// 辅助函数：创建链表
ListNode* createList(vector<int>& nums) {
    if (nums.empty()) return nullptr;
    
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    
    for (int i = 1; i < nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    
    return head;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* cur = head;
    cout << "[";
    while (cur != nullptr) {
        cout << cur->val;
        if (cur->next != nullptr) cout << ",";
        cur = cur->next;
    }
    cout << "]";
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    Solution solution;
    
    // 测试案例1：回文链表 [1,2,2,1]
    cout << "测试案例1: ";
    vector<int> nums1 = {1, 2, 2, 1};
    ListNode* head1 = createList(nums1);
    printList(head1);
    bool result1 = solution.isPalindrome(head1);
    cout << " -> " << (result1 ? "true" : "false") << " (期望: true)" << endl;
    deleteList(head1);
    
    // 测试案例2：非回文链表 [1,2]
    cout << "测试案例2: ";
    vector<int> nums2 = {1, 2};
    ListNode* head2 = createList(nums2);
    printList(head2);
    bool result2 = solution.isPalindrome(head2);
    cout << " -> " << (result2 ? "true" : "false") << " (期望: false)" << endl;
    deleteList(head2);
    
    // 测试案例3：单节点链表 [1]
    cout << "测试案例3: ";
    vector<int> nums3 = {1};
    ListNode* head3 = createList(nums3);
    printList(head3);
    bool result3 = solution.isPalindrome(head3);
    cout << " -> " << (result3 ? "true" : "false") << " (期望: true)" << endl;
    deleteList(head3);
    
    // 测试案例4：空链表
    cout << "测试案例4: ";
    ListNode* head4 = nullptr;
    cout << "[]";
    bool result4 = solution.isPalindrome(head4);
    cout << " -> " << (result4 ? "true" : "false") << " (期望: false，根据你的实现)" << endl;
    
    // 测试案例5：奇数长度回文 [1,2,3,2,1]
    cout << "测试案例5: ";
    vector<int> nums5 = {1, 2, 3, 2, 1};
    ListNode* head5 = createList(nums5);
    printList(head5);
    bool result5 = solution.isPalindrome(head5);
    cout << " -> " << (result5 ? "true" : "false") << " (期望: true，但你的算法可能返回false)" << endl;
    deleteList(head5);
    
    // 测试案例6：相同元素 [2,2,2,2]
    cout << "测试案例6: ";
    vector<int> nums6 = {2, 2, 2, 2};
    ListNode* head6 = createList(nums6);
    printList(head6);
    bool result6 = solution.isPalindrome(head6);
    cout << " -> " << (result6 ? "true" : "false") << " (期望: true)" << endl;
    deleteList(head6);
    
    return 0;
}